package com.niuke;

import com.leetCode.tree.TreeNode;
import com.pojo.ListNode;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-10 10:25:44
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-10     张李鑫                     1.0         1.0 Version
 */
public class JZ54 {
    /**
     * 描述
     * 给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。
     * 1.返回第k小的节点值即可
     * 2.不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1
     * 3.保证n个节点的值不一样
     * <p>
     * <p>
     * 数据范围： 0 \le n \le10000≤n≤1000，0 \le k \le10000≤k≤1000，树上每个结点的值满足0 \le val \le 10000≤val≤1000
     * 进阶：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
     */

    public static int KthNode(TreeNode proot, int k) {
        Queue<Integer> q = new PriorityQueue<>();
        process(proot, q);
        while (k > 1) {
            q.poll();
            k--;
        }
        return k == 1 ? (q.isEmpty() ? -1 : q.poll()) : -1;
    }

    private static void process(TreeNode proot, Queue<Integer> q) {
        if (proot == null) {
            return;
        }
        process(proot.left, q);
        q.add(proot.val);
        process(proot.right, q);
    }

    public static void main(String[] args) {
        TreeNode listNode = new TreeNode(5);
        TreeNode listNode1 = new TreeNode(3);
        TreeNode listNode2 = new TreeNode(7);
        TreeNode listNode3 = new TreeNode(2);
        TreeNode listNode4 = new TreeNode(4);
        TreeNode listNode5 = new TreeNode(6);
        TreeNode listNode6 = new TreeNode(8);

        listNode.left = listNode1;
        listNode.right = listNode2;
        listNode1.left = listNode3;
        listNode3.right = listNode4;
        listNode2.left = listNode5;
        listNode2.right = listNode6;


        System.out.println(KthNode(listNode, 1));


    }
}
